import java.util.Currency;
import java.util.IllegalFormatFlagsException;

//左子树上的节点都小于根节点值，右节点的值都大于根节点的值
public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val=val;
        }
    }
    public TreeNode root;
    //搜索是否存在val值，时间复杂度为一般情况：O(log2n)，最坏情况是单分支树，此时时间复杂度为O(N);
    public boolean search(int val) {
        TreeNode cur=root;
        while(cur!=null) {
            if(cur.val==val) {
                return true;
            }
            else if(cur.val<val) {
                cur=cur.right;
            }else {
                cur=cur.left;
            }
        }
        return   true;
    }
    //插入
    public void insert(int val) {
        TreeNode node=new TreeNode(val);
        if(root==null) {
            root=node;
            return ;
        }
        TreeNode curParent=null;
        TreeNode cur=root;
        while(cur!=null) {
            if(cur.val==val) {
                return;
            }else if(cur.val<val) {
                curParent=cur;
                cur=cur.right;
            }else {
                curParent=cur;
                cur=cur.left;
            }
        }
        if(curParent.val>val) {
            curParent.left=node;
        }else {
            curParent.right=node;
        }
    }
    //删掉val 值的节点
    public void remove(int val) {
        TreeNode cur=root;
        //先找一下看一下有没有没有的话不用删除
        TreeNode curParent=null;
        while(cur!=null) {
            if(cur.val==val) {
                removeNode(curParent, cur);
            }else if(cur.val>val) {
                curParent=cur;
                cur=cur.left;
            }else {
                curParent=cur;
                cur=cur.right;
            }
        }
    }
    private void removeNode(TreeNode p,TreeNode c ) {
        if(c.left==null) {
            if(c==root) {
                root=c.right;
            }
            if(p.left==c) {
                p.left=c.right;
            }else {
                p.right=c.right;
            }
        }else if(c.right==null) {
            if(c==root) {
                root=c.left;
            }
            if(p.left==c) {
                p.left=c.left;
            }else{
                p.right=c.left;
            };
        }//左右都不为空
        else {
            TreeNode targe=c.right;
            TreeNode targeParent=c;
            while(targe.left!=null) {
                targeParent=targe;
                targe=targe.left;
            }
            c.val=targe.val;
            if(targeParent==c)
                targeParent.right=targe.right;
            else {
                targeParent.left=targe.right;
            }

        }
    }
}